/*
https://leetcode.cn/problems/finding-mk-average/solution/qiu-chu-mk-ping-jun-zhi-by-leetcode-solu-sos6/
 */
import java.util.*;

public class Solution1825 {

    int m,k;
    int now=0;
    Queue<Integer> queue=new LinkedList<>();
    TreeMap<Integer,Integer> left=new TreeMap<>();
    TreeMap<Integer,Integer> mid=new TreeMap<>();
    TreeMap<Integer,Integer> right=new TreeMap<>();
    int s=0;


    public Solution1825(int m, int k) {
        this.m=m;
        this.k=k;
    }

    public void addElement(int num) {
        queue.offer(num);
        now++;
        if (now==m){
            List<Integer> temp = new ArrayList<>(queue);
            temp.sort(Comparator.comparingInt(a -> a));
            for (int i=0;i<k;i++){
                left.put(temp.get(i),left.getOrDefault(temp.get(i),0)+1);
            }
            for (int i=k;i<m-k;i++){
                mid.put(temp.get(i),mid.getOrDefault(temp.get(i),0)+1);
                s+=temp.get(i);
            }
            for (int i=m-k;i<m;i++){
                right.put(temp.get(i),right.getOrDefault(temp.get(i),0)+1);
            }
        }else if (now>m){
            if (left.size()>0 && num<left.lastKey()){
                left.put(num,left.getOrDefault(num,0)+1);
                left.put(left.lastKey(),left.get(left.lastKey())-1);
                mid.put(left.lastKey(),mid.getOrDefault(left.lastKey(),0)+1);
                s+=left.lastKey();
                if (left.get(left.lastKey())==0){
                    left.remove(left.lastKey());
                }
            }else if (right.size()>0 && num>right.firstKey()){
                right.put(num,right.getOrDefault(num,0)+1);
                right.put(right.firstKey(),right.get(right.firstKey())-1);
                mid.put(right.firstKey(),mid.getOrDefault(right.firstKey(),0)+1);
                s+=right.firstKey();
                if (right.get(right.firstKey())==0){
                    right.remove(right.firstKey());
                }
            }else {
                mid.put(num,mid.getOrDefault(num,0)+1);
                s+=num;
            }
            int t=queue.poll();
            if (left.size()>0 && t<=left.lastKey()){
                left.put(t,left.get(t)-1);
                if (left.get(t)==0){
                    left.remove(t);
                }
                left.put(mid.firstKey(),left.getOrDefault(mid.firstKey(),0)+1);
                mid.put(mid.firstKey(),mid.get(mid.firstKey())-1);
                s-=mid.firstKey();
                if (mid.get(mid.firstKey())==0){
                    mid.remove(mid.firstKey());
                }
            }else if (right.size()>0 && t>=right.firstKey()){
                right.put(t,right.get(t)-1);
                if (right.get(t)==0){
                    right.remove(t);
                }
                right.put(mid.lastKey(),right.getOrDefault(mid.lastKey(),0)+1);
                mid.put(mid.lastKey(),mid.get(mid.lastKey())-1);
                s-=mid.lastKey();
                if (mid.get(mid.lastKey())==0){
                    mid.remove(mid.lastKey());
                }
            }else {
                s-=t;
                mid.put(t,mid.get(t)-1);
                if (mid.get(t)==0){
                    mid.remove(t);
                }
            }
        }
    }

    public int calculateMKAverage() {
        if (now<m){
            return -1;
        }else {
            return s/(m-2*k);
        }
    }

    public static void main(String[] args) {
        Solution1825 solution1825=new Solution1825(3,1);
        solution1825.addElement(3);
        solution1825.addElement(1);
        System.out.println(solution1825.calculateMKAverage());
        solution1825.addElement(10);
        System.out.println(solution1825.calculateMKAverage());
        solution1825.addElement(5);
        solution1825.addElement(5);
        solution1825.addElement(5);
        System.out.println(solution1825.calculateMKAverage());
    }
}
